package main

import "fmt"

func main() {
	fmt.Println(levelOrderBottom(&TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
		},
		Right: &TreeNode{
			Val: 3,
		},
	}))
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrderBottom(root *TreeNode) (ans [][]int) {
	if root == nil {
		return [][]int{{}}
	}
	var queue []*TreeNode
	queue = append(queue, root)
	for len(queue) != 0 {
		k := 0
		var ansLevel []int
		for l := len(queue); k < l; k++ {
			ansLevel = append(ansLevel, queue[k].Val)
			if queue[k].Left != nil {
				queue = append(queue, queue[k].Left)
			}
			if queue[k].Right != nil {
				queue = append(queue, queue[k].Right)
			}
		}
		ans = append(ans, ansLevel)
		queue = queue[k:]
	}
	for i, j := 0, len(ans)-1; i < j; {
		ans[i], ans[j] = ans[j], ans[i]
		i++
		j--
	}
	return ans
}
